﻿#pragma once
#include "BStruct.h"

/// <summary>
/// B 树
/// </summary>
class BTreeClass
{
public:
	BTreeClass();

	virtual ~BTreeClass();

	/// <summary>
	/// 添加数据
	/// </summary>
	/// <param name="value"></param>
	void insert(int value);

	/// <summary>
	/// 查找节点
	/// </summary>
	/// <param name="key"></param>
	/// <returns></returns>
	FindResult* const findNode(int key);

	/// <summary>
	/// 删除数据
	/// </summary>
	/// <param name="key"></param>
	void delKey(int key);

protected:

	/// <summary>
	/// 创建一个新节点
	/// </summary>
	/// <returns></returns>
	/// </summary>
	/// <param name="index">索引下标</param>
	/// <param name="key">索引下标对应的值</param>
	/// <param name="num">当前元素数目</param>
	/// <returns></returns>
	BStruct* createNewNode(int index = 0, int key = 0, size_t num = 0);

	/// <summary>
	/// 按条件找到插入位置
	/// </summary>
	/// <param name="value"></param>
	void insertNonFull(BStruct* node, int value);

	/// <summary>
	/// 分裂B树，生长
	/// </summary>
	void splitBTreeLeaf(BStruct* parent, BStruct* node, size_t pos);

	/// <summary>
	/// 释放b树
	/// </summary>
	/// <param name="node"></param>
	void destroy(BStruct* node);

private:

	BStruct* root;

	/// <summary>
	///  添加元素，以及让数据从小到大排列
	/// </summary>
	/// <param name="node"></param>
	/// <param name="value"></param>
	/// <returns></returns>
	void addElementByCondition(BStruct* node, int value) const;

	/// <summary>
	/// 节点没有分支时添加
	/// </summary>
	/// <param name="node"></param>
	void noBranchByInsert(BStruct* node);

	/// <summary>
	/// 节点生长时添加
	/// </summary>
	/// <param name="node"></param>
	void nodeGrowByInsert(BStruct* parent, BStruct* node);

	/// <summary>
	/// 节点分叉
	/// </summary>
	/// <param name="parent">父节点</param>
	/// <param name="node">子节点</param>
	/// <param name="pos">子节点所在的位置</param>
	void nodeBifurcation(BStruct* parent, BStruct* node, size_t pos);

	/// <summary>
	/// 留下中间节点
	/// </summary>
	void keepTheMiddleNode(BStruct* node);

	/// <summary>
	/// 辅助查找
	/// </summary>
	/// <param name="node"></param>
	/// <param name="key"></param>
	/// <returns></returns>
	FindResult* auxiliaryByFind(BStruct* node, int key);

	/// <summary>
	/// 获取要插入的位置
	/// </summary>
	/// <param name="node"></param>
	/// <returns></returns>
	unsigned int getPos(BStruct* node, int value);

	/// <summary>
	/// 获取左边节点的最右边的值
	/// </summary>
	/// <returns></returns>
	int pareseRightDateBySturct(BStruct* node);

	/// <summary>
	/// 获取右边节点的最右边的值
	/// </summary>
	/// <returns></returns>
	int pareseLeftDateBySturct(BStruct* node);

	/// <summary>
	/// 辅助删除
	/// </summary>
	/// <param name="node"></param>
	void delNonFull(FindResult* res);

	/// <summary>
	/// 删除元素并前移
	/// </summary>
	/// <param name="node"></param>
	/// <param name="pos"></param>
	void deleteElementandMoveForward(BStruct* node, unsigned int pos);

	/// <summary>
	/// 合并节点
	/// </summary>
	/// <param name="left"></param>
	/// <param name="sibling"></param>
	void merge(FindResult* data);
};
